//
//  349. 两个数组的交集.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/12.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution349 {
    // 解法1,时间复杂度为o(n)
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var set1: Set<Int> = []
        var set2: Set<Int> = []
        for item in nums1 {
            set1.insert(item)
        }
        for item in nums2 {
            if set1.contains(item) {
                set2.insert(item)
            }
        }
        return  Array(set2)
    }
    // 解法2,时间复杂度为nlogn
    // 先排序，然后用双指针法
    func intersection2(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        let nums1 = nums1.sorted()
        let nums2 = nums2.sorted()
        var index1 = 0
        var index2 = 0
        var result: [Int] = []
        while index1 < nums1.count, index2 < nums2.count {
            if nums1[index1] < nums2[index2] {
                index1 += 1
            } else if nums1[index1] == nums2[index2] {
                let pre = result.last
                if pre != nums1[index1]{
                    result.append(nums1[index1])
                }
                index1 += 1
                index2 += 1
            } else {
                index2 += 1
            }
        }
        return result
    }
    static func test() {
        let solu = Solution349()
//        let nums1 = [4,9,5]
//        let nums2 = [9,4,9,8,4]
        let nums1 = [1,2,2,1]
        let nums2 = [2,2]
        let flag = solu.intersection2(nums1, nums2)
        print(flag)
    }
}
